package algorthm.systemTraning.manacher;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @className: Manacher
 * @Description:
 * @Author: wangyifei
 * @Date: 2024/4/30 16:57
 */
public class Manacher {
    private static Logger logger = LoggerFactory.getLogger(Manacher.class);

    /**
     * 查找最大回子文字串
     * @param args
     */
    public static void main(String[] args) {
        String line = "aaa12344321";
        System.out.println(findMaxHui(line));
    }
    public static int findMaxHui(String line){
        char[] chars = line.toCharArray();
        List<String> list = new ArrayList();
        for(char c : chars){
            list.add(c+"");
        }
        String join = "#" + String.join("#", list) + "#";
        int max = 0 ;
        for(int i = 0 ; i < join.length() ; i++){
            int j = 1 ;
            int m = 1 ;
            while((i - j >= 0) && (i + j < join.length())){
                if(join.charAt(i-j) == join.charAt(i+j)){
                    m+=2;
                }else{
                    break;
                }
                j++;
            }
            max = Math.max(max , m);
        }
        return max/2 ;
    }
}
